package lc.q350_400;

public class Q372 {

    public static void main(String[] args) {
        Q372 q372 = new Q372();
        System.out.println(q372.superPow(2147483647, new int[]{2, 0, 0}));
    }

    public int superPow(int a, int[] b) {
        if (a > 1337) {
            return superPow(a % 1337, b);
        }
        int n = b.length;
        int ans = 1;
        for (int i = n - 1; i >= 0; i--) {
            ans = (int)((long)ans * pow(a, b[i]) % 1337);
            a = pow(a, 10);
        }
        return ans;
    }

    private int pow(int a, int n) {
        // 对半
        int res = 1;
        while (n != 0) {
            if (n % 2 != 0) {
                res = (int)((long)res * a % 1337);
            }
            a = (int)((long) a * a % 1337);
            n = n / 2;
        }
        return res;
    }
}
